對抗式搜尋與約束滿足

歡迎來到第三課，人工智能概念（PolyU COMP5511）。本節課，我們將從單智能體路徑尋找轉向對抗式搜尋，智能體在競爭性的多智能體環境中運行。我們還將介紹約束滿足問題 (CSPs)，這是一種尋找滿足特定限制條件的狀態，而非路徑的範式。

核心概念

對抗式搜尋： 著重於演算法，例如極小極大值 (Minimax) 與極小極大值剪枝 (Alpha-Beta Pruning)，以對抗智能對手並做出理性決策。
蒙地卡羅樹搜尋 (MCTS)： 探索機率性決策，是現代遊戲 AI（例如 AlphaGo）的基礎。
約束滿足： 使用變數、定義域和約束來建模問題，透過 回溯搜尋 (Backtracking) 與 局部搜尋 (Local Search)）的基礎。

複雜度分析

在對抗環境中，搜尋空間的複雜度通常由遊戲的分支因子 $b$ 和深度 $d$ ，導致計算成本為： $O （ b^{d} ）$ 。這種指數級的增長需要有效的剪枝策略，例如 Alpha-Beta 剪枝。

典範轉移警告

與標準搜尋（例如 A* 或 BFS，環境是靜態的）不同，對抗式搜尋 假設環境（對手）會積極嘗試最小化你的成功。而在 CSPs 中，動作的順序不如最終指派的有效性重要。

概念性偽代碼：智能體類型

# 對抗式智能體（賽局理論）
functionDecide_Move（state):
returnMaximize_Utility（Predict_Opponent_Minimization（state))
# CSP 求解器（約束邏輯）
functionSolve_CSP（variables, constraints):
ifAll_Constraints_Satisfied（assignment):
returnassignment
else：
returnBacktrack_Search（variables）

課程路線圖

從搜尋（第二課）轉向策略決策（第三課）。